package com.lans.SortAlgorithm;

import java.util.Arrays;

/**
 * @author: lans
 * @date: 2025/2/11
 * @name: 刘宇
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {5,2,4,1,56,87,212,3};
        int[] temp = new int[arr.length];
        mSort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 向下分解的过程
     * @param arr 无序序列
     * @param left 左指针
     * @param right 右指针
     * @param temp 临时数组
     */
    public static void mSort(int[] arr,int left,int right,int[] temp){
        if(left<right){
            int mid = (left+right)/2;
            //向左进行分解
            mSort(arr,left,mid,temp);
            //向右进行分解
            mSort(arr,mid+1,right,temp);
            //无法分解后 归并
            mergeSort(arr,left,right,mid,temp);
        }
    }
    //开始归并
    public static void mergeSort(int[] arr,int left,int right,int mid,int[] temp){
        int i = left;//左边序列的开始位置
        int j = mid+1;//右边序列的开始位置
        int e = 0;//用来记录临时数组的下标
        while(i<=mid&&j<=right){
            if(arr[i]<=arr[j]){
                temp[e] = arr[i];
                e++;
                i++;
            }else{
                temp[e] = arr[j];
                e++;
                j++;
            }
        }
        //将左边有序序列剩余的元素平移到临时数组中来
        while(i<=mid){
            temp[e] = arr[i];
            e++;
            i++;
        }
        //将右边的有序序列剩余的元素平移到临时数组中来
        while(j<=right){
            temp[e] = arr[j];
            e++;
            j++;
        }
        //将临时数组元素拷贝回原数组
        e= 0 ;
        while(left<=right){
            arr[left] = temp[e];
            left++;
            e++;
        }
    }
}